package SortTemplate;

public class BucketSort {
    public static void commonSort(int[] num) {
        int max = num[0];
        for (int i = 0; i < num.length; i++) {
            if (num[i] > max) {
                max = num[i];
            }
        }

        // 创建一个下标为原始数组中最大值的桶数组,该桶数组的下标代表元素，该数组下标所对应的值代表这个值出现的次数

        int[] bucketArray = new int[max + 1];

        // 再次遍历原始数组，得到原数组中存在的各个元素，以及出现的次数
        for (int i = 0; i < num.length; i++) {
            bucketArray[num[i]]++;
        }

        // 遍历桶数组,外层循环从桶的第一位开始（即下表为零）；内层循环遍历桶数组中下标为i的值出现的次数
        int index = 0;
        for (int i = 0; i < bucketArray.length; i++) {
            for (int j = 0; j < bucketArray[i]; j++) {
                num[index++] = i;
            }
        }
    }

    public static void sortArr(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        String strLen = max + "";
        int maxLen = strLen.length();// 最大位数
        int[][] buckets = new int[10][arr.length]; // 分桶
        int[] element = new int[10];// 桶中的数据量
        int n = 1;
        for (int i = 0; i < maxLen; ++i) {
            for (int j = 0; j < arr.length; ++j) {
                int cur = arr[j] / n % 10; // 数组中各个元素位置的相应数字
                buckets[cur][element[cur]] = arr[j];
                element[cur]++;
            }
            int idx = 0;
            // 遍历桶并放回对应位置
            for (int j = 0; j < element.length; j++) {
                for (int k = 0; k < element[j]; k++) {
                    arr[idx] = buckets[j][k];
                    ++idx;
                }
                element[j] = 0;// 清空该桶计数
            }
            n *= 10;
        }

    }
}
